The Internet includes a network of interconnected routers that route customer data packets over one or more links between a source Internet Protocol (IP) address and a destination IP address. Successful routing of customer data packets requires that a logical path (i.e., a collection of one or more links) exist in the network between the source IP address and destination IP address for that packet. Based on the contents of its routing table, each router along the path determines the best hop on which to send each packet in order to deliver the packets to the ultimate destination. Assuming the network possesses sufficient physical redundancy (e.g., multiple routers, multiple links), the network can dynamically redefine paths using protocols such as the Border Gateway Protocol (BGP) or Open Shortest Path First (OSPF) protocol, in case of a router or link failure. The use of such protocols ensures that no one router or link failure disrupts the flow of packets between a source IP address and destination IP address.
FIG. 1 depicts an example network 100 of routers. The network 100 includes eight different routers (identified as routers 1-8) that are interconnected through various links. For exemplary purposes, router 1 is identified as a source router and routers 7 and 8 are identified as destination routers, routers A and B respectively. As depicted in FIG. 1, traffic from the source router 1 can reach the destination routers through many different routes. That is, the path between the source router and the destination routers include multiple redundant routes. Redundant routes are different routes that have the same source and destination. As is known in the field of IP networks, the routers employ route tables to keep track of the plurality of different routes that are available to reach a destination IP address from a particular router. For example, source router 1 utilizes a route table to track the available routes to the two destination routers 7 and 8.
When redundant routes exist for a given destination, some routes are preferred over other routes. For example, route preference may be based on the numbers of hops (other routers) that are required between the source and the destination or on an amount of bandwidth available on the links along the route. In FIG. 1, the numbers next to the logical paths connecting the routers indicate the number of hops between the depicted routers. As one example, a data packet makes 12 hops to travel from router 1 to router 2. Often times, redundant routes are stored in a route table in a preferential order, e.g. the most preferred route is stored first, the next most preferred route is stored second, etc.
FIG. 2 depicts a conventional routing table 200. Referring to FIG. 1 in conjunction with FIG. 2, the route table 200 stores example routes from the source to destination A and destination B. In the example, the routes to Destination A include Routes A.1, A.2, A.3 . . . A.N where N is an integer value of the Nth route available to Destination A. Similarly, the routes to Destination B include Routes B.1, B.2, B.3, B.4 . . . B.N.
Conventional route tables are responsible for storing thousands, sometimes tens of thousands of routes. Because the storage capacity of the route table is limited, once the router reaches it's storage capacity, the router can become overloaded with routes thereby causing new routes to be dropped indiscriminately. FIG. 3 depicts a flowchart of a conventional scheme for managing routes. First, at block 310 a volume of stored routes is identified in the router. Next, at block 320, a determination is made as to whether the volume of stored routes has reached the storage capacity of the router. If the volume of routes has not reached the storage capacity, all incoming routes are stored in the route table at block 330. If the volume of routes has reached the storage capacity, all incoming routes are discarded at block 340. That is, the routes are indiscriminately discarded without regard to the relative preference or the redundant nature of some of the routes. This is an extremely inefficient use of the router's limited storage capacity.
Therefore, what is needed is a method and system that addresses the above-described short-comings of the conventional methodology. The method and system should be simple, cost effective and capable of being easily adapted into existing technology. The present invention addresses such a need.